/*
 * @lc app=leetcode.cn id=131 lang=cpp
 *
 * [131] 分割回文串
 *
 * https://leetcode.cn/problems/palindrome-partitioning/description/
 *
 * algorithms
 * Medium (73.47%)
 * Likes:    1723
 * Dislikes: 0
 * Total Accepted:    358.3K
 * Total Submissions: 487.7K
 * Testcase Example:  '"aab"'
 *
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * 
 * 回文串 是正着读和反着读都一样的字符串。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：s = "a"
 * 输出：[["a"]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * s 仅由小写英文字母组成
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    bool isPalindrome(const string& s) {
        int l = 0, r = s.size() - 1;

        for (; l < r; l++, r--)
            if (s[l] != s[r])
                return false;

        return true;
    }

    void BackTracking(vector<vector<string>>& result, vector<string>& path,
        const string& s, int startIndex) {
        
        if (startIndex >= s.size()) {   //分割线 startIndex 到末尾, 添加结果
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i < s.size(); i++) {
            //截取每次分割的字串, 在 [ startIndex, i ] 这个区间中
            auto sub = s.substr(startIndex, i - startIndex + 1);
            if (isPalindrome(sub))  //判断是否回文
                path.push_back(sub);
            
            else
                continue;
            
            BackTracking(result, path, s, i + 1);

            path.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        //分割问题和组合问题差不多
        //分割过程和选取元素的过程大致相同

        /*
                        aab
                a|ab            aa|b        aab|
        a|a|b       a|ab|       aa|b|
        a|a|b|
        */

        //如上述的树形结构所示, 切割过程和组合中的选取元素过程大致相同

        vector<vector<string>> result;
        vector<string> path;

        BackTracking(result, path, s, 0);

        return result;
    }
};
// @lc code=end

